The present invention relates generally to on-board, vehicle navigation systems, and more particularly, to such a system usable with a positioning system, such as a global positioning system (GPS), for accurately determining the position of a mobile receiver, such as a GPS receiver, by reducing relatively low and high frequency noise components corrupting the signals received from the GPS satellites using predictive and map-matching algorithms.
On-board vehicle navigation systems often rely on the Global positioning System (GPS) for sensing an absolute or actual position of a vehicle hosting the on-board system. Such on-board navigation systems include a mobile GPS receiver installed in the vehicle, and typically integrated with a host of other sensors, such as an odometer and/or gyroscope. The mobile GPS receiver senses a vehicle position, referred to as a GPS position, based on signals received at the GPS receiver from a plurality of GPS satellites, as is known.
However, the accuracy of the GPS position suffers because of problems associated with multipath reflections of the GPS satellite signals, and from artificial accuracy degradation caused by Selective Availability (SA) resulting from military control of the GPS satellites. For example, SA can induce a positional error on the order of one-hundred meters, with a root-mean-square (RMS) error of approximately forty meters. In addition to the multipath and SA, clock jitter and transient loss-of-signal conditions further degrade GPS position accuracy.
U.S. Pat. No. 5,087,919 discloses one application of an on-board navigation system, wherein GPS positions from a GPS receiver are matched to street locations stored in a map database of the on-board system. The on-board system displays the map matched GPS positions along with map based topological information, such as a city street network. The system uses a two step process to match a GPS position with a street represented in the map database. First, the process identifies candidate streets represented in the map database within a predetermined distance of the GPS position. Second, beginning with the nearest candidate street, the process steps individually through the candidate streets to identify a candidate street having a heading or direction xe2x80x9csubstantially matchingxe2x80x9d a heading or travelling direction of the vehicle, determined based on the GPS positions.
Requiring a xe2x80x9csubstantial matchxe2x80x9d between the street and vehicle headings tends to be too strict or limiting a map matching criterion because it does not take into account error in the vehicle heading caused by the error or noise sources previously mentioned. Consequently, the map matching process unnecessarily eliminates a valid street (where the vehicle is actually located), and most likely all streets, from consideration when the vehicle heading and the valid street heading fail to meet the substantially matching criterion because of such error. On the other hand, if the criterion is substantially relaxed or significantly expanded to accommodate such error, the map matching process tends to erroneously select invalid streets where the vehicle is not located because the criterion is insufficiently selective.
Accordingly, in a map matching algorithm for matching a position of a receiver derived from a satellite signal with a probable position on a street represented in a map database, there is a need to reduce the probability that a valid street is eliminated from consideration because of a corrupted vehicle heading, and that an invalid street is erroneously selected.
Emergency vehicle applications of the on-board navigation system require a rapid, accurate response from the on-board navigation system. Emergency vehicle applications include navigation or fleet management of emergency vehicles, such as police and fire fighting vehicles, carrying the on-board navigation system. In such applications, it is highly desirable to associate the position of the emergency vehicle with a street on a city street network, within approximately five seconds after activating the GPS receiver in the on-board navigation system. The position indicated by the on-board system after five seconds, and typically displayed as mentioned above, must accurately associate the emergency vehicle with the correct street on which the vehicle is travelling, so as to reduce navigational errors and thus decrease emergency vehicle response time.
Accordingly, in an on-board navigation system including a GPS receiver, a need exists for rapidly and accurately associating a position derived by the GPS receiver with a position on a map, such as street position, within five seconds or less after activating the receiver.
On-board vehicle navigation systems commonly include a predictive filter, such as a Kalman Filter (KF), to improve the accuracy of the degraded GPS positions, and to integrate the GPS positions with information from the other sensors. As is known, the KF predictively filters a measured variable over time to derive expected or predicted values of the variable. For example, Kalman filters typically filter a series of GPS positions to derive a series of predicted positions of the GPS receiver. In deriving such predictions, the KF applies a weighing function, known as the Kalman gain, which is optimized by the Kalman filtering process to produce a minimum error variance. An important aspect of the KF includes adaptive adjustment of the Kalman gain responsive to continuous feedback of the error variance.
Importantly, the KF provides an accurate prediction only when the measured variable supplied to the KF is corrupted by uncorrelated or white noise. This means the noise corrupting consecutive measurements, such as consecutive GPS positions, must be uncorrelated for the KF to work effectively. Otherwise, correlated noise, inducing correlated error in the GPS positions, tends to throw the Kalman gain, and thus the predictions, off-track. Stated otherwise, if the noise corrupting the GPS positions has a time constant substantially greater than the time between consecutive GPS position measurements, then such low frequency noise tends to render the KF ineffective. As a result, the KF is ineffective at removing the relatively low frequency or slowly varying noise component from the GPS positions. On the other hand, in the absence of such low frequency noise, if the noise corrupting the GPS positions has a time constant on the order of, or less than, the time between consecutive GPS position measurements, then the KF arrives at accurate predictions. As a result, the KF can filter such a relatively high frequency or fast varying noise component from the GPS positions.
Because the KF responds favorably and unfavorably to high (uncorrelated) and low (correlated) frequency noise, respectively, it is instructive to broadly categorize the noise/errors due to Selective Availability, multipath, clock jitter, and transient-loss-of-signal as having high and/or low frequency noise components. Selective Availability has been empirically determined to vary slowly over hundreds of seconds, and is thus considered a low frequency error bias corrupting GPS positions, and consequently, KF predictions. This is especially true for modem GPS receivers that provide frequent GPS position updates, for example, once every second. The effects of multipath can vary drastically from second to second as the mobile GPS receiver travels quickly past, for example, buildings, trees, and bridges. On the other hand, multipath effects can vary slowly as the mobile receiver travels past, for example, large bodies of water. Multipath errors thus exhibit both low and high frequency noise components. Transient-loss-of-signal is considered to exhibit both low and high frequency noise components, while clock jitter is characteristically, only short term in nature.
U.S. Pat. No. 5,416,712 discloses a system for reducing correlated error corrupting GPS positions. The system includes a modified KF in combination with external sensors, such as an odometer and a gyroscope, to reduce errors. The modified KF includes error variance and Kalman gain equations which approximately model the correlated error. Simply stated, the modified equations increase the gain floor of the KF to account for correlated error, to enable the modified KF to filter correlated, as well as uncorrelated, error.
This approach to reducing correlated error had several disadvantages. First, it requires a relatively complex modification to an otherwise standard or commercial-off-the-shelf KF, thus adding substantial complexity and cost to the on-board navigation system. Second, the modified KF only approximates correlated error due to SA, and thus provides an approximate solution limited in scope. Third, the modified KF tends to ignore correlated error from sources other than SA, such as multipath, because the correlated error model used by the modified KF is tuned to SA. Another disadvantage of the system is the requirement for external sensors in addition to the GPS receiver, further increasing complexity and cost of the on-board navigation system.
Another known approach to reducing correlated error in GPS positions is to use differential GPS receiver technology. Differential GPS technology disadvantageously requires a GPS reference base station in addition to the mobile GPS receiver, thus increasing cost and complexity of the overall navigation system.
Accordingly, a need exists for accurately determining the position of a mobile receiver by reducing low and high frequency noise components corrupting signals received from a positioning system, such as the GPS satellite system. A related need exists for removing such noise from predicted positions derived by predictively filtering the signals received from the positioning system, without using external sensors or differential GPS technology.
It is, therefore, an object of the present invention to substantially overcome the above-identified problems and substantially fulfill the above-identified needs.
It is another object of the present invention to accurately determine the position of a mobile receiver in an on-board, vehicle navigation system by reducing relatively low and high frequency noise components corrupting position signals from a positioning system, such as the GPS satellite system.
Another object is to remove relatively low and high frequency noise components from predicted positions derived by predictively filtering position signals from a positioning system, without using external sensors or differential GPS technology.
It is another object of the present invention to rapidly and accurately associate position signals from a positioning system with a position on a street represented in a map database within five seconds or less.
Another object is to map match a position of a receiver derived from a satellite signal with a probable position on a street represented in a map database using a heading of the receiver derived from the satellite signal, and to reduce the probability that a valid street is eliminated from consideration because of error in the heading of the receiver, and that an invalid street is erroneously selected.
In accordance with the present invention, an accurate position of a mobile receiver is determined using a received positional signal having relatively low and high frequency noise components corrupting the positional accuracy of the positional signal. Positions of the mobile receiver are derived using the received positional signal. The positions are predictively filtered by a predictive filter to derive predicted positions of the mobile receiver. The predicted positions are corrupted by the low and high frequency noise components. A turn of the mobile receiver is detected and a first positional error associated with the turn is derived. The first positional error represents a distance between 1) a predicted turn position derived using the predicted positions and 2) a probable turn position of where the mobile receiver probably turned on a navigable route represented in a map database and selected from the map database using a map matching algorithm.
The first positional error is used as a low frequency feedback correction factor to correct positions of the mobile receiver derived using the received signal and after the turn is detected. Such low frequency correction advantageously removes the low frequency noise component from the positions before the positions are applied to the predictive filter.
Each of the positions derived after the turn is detected is corrected using the low frequency correction factor to derive corrected positions. Each of the corrected positions is applied to the predictive filter along with a second positional error associated with each of the corrected positions and representative of the high frequency noise component, to advantageously derive filtered, predicted positions substantially free of the low and high frequency noise components. Each second positional error represents a distance between the associated corrected position and a navigable route on which the mobile receiver is probably located, and is advantageously used as a high frequency feedback correction, and more specifically, as a variance error to advantageously control the gain of the predictive filter.
In accordance with another aspect of the present invention, a map matching algorithm is used to match a predicted position of a mobile receiver with a probable position of the mobile receiver coinciding with a known navigable route of where the mobile receiver is probably located. The algorithm includes identifying candidate navigable routes in a map database within a predetermined distance of the predicted position. A weighted distance between each of the navigable routes and the predicted position is derived using a shortest distance and a difference in direction between each candidate navigable route and the mobile receiver. The weighted distance is derived using a modified cosine weighting function that adds distance to the shortest distance depending on the difference in direction between the candidate route and the mobile receiver. The probable position coincides with the navigable route associated with the minimum weighted distance.
In accordance with another aspect of the present invention, a method of rapidly associating a position of a mobile receiver with a navigable route accessible in a map database is disclosed. The method includes seeding a predictive filter with an initial value indicative of an erroneous current position value of the mobile receiver displaced a predetermined minimum distance from a known approximate position of the mobile receiver to establish an initial gain of the predictive filter. A positional signal is received over m time periods and position values of the mobile receiver are derived over the m time periods using the received positional signal. Predicted position values of the mobile receiver are derived over the m time periods by predictively filtering the position values with the predictive filter. A probable position of the mobile receiver is determined at an end of the m time periods using a current predicted position value. The probable position coincides with a navigable route on which the mobile receiver is probably positioned at the end of the m time periods. The probable position is derived using the map matching algorithm described above.
In accordance with another aspect of the present invention, a method of accurately determining the position of a mobile receiver is disclosed. The method includes detecting a turn of the mobile receiver using a received positional signal and deriving a first positional offset associated with the turn and representative of a low frequency noise component corrupting the positional accuracy of the received signal. A position value of the mobile receiver is derived using the received positional signal after detecting the turn, and the position value is corrected with the first positional offset associated with the turn to derive a corrected position value. The corrected position value is applied to a filter along with a second positional offset associated with the corrected position value and representative of a high frequency noise component corrupting the positional accuracy of the received signal to derive a filtered position value substantially free of the low and high frequency noise components.
In accordance with another aspect of the present invention, a method of accurately determining the position of a mobile receiver includes receiving a positional signal over time intervals T1 through Tm, where T represents the duration of each time interval and the subscript represents the position of each time interval in the sequence of time intervals T1 through Tm. Position values of the mobile receiver at time intervals T1 through Tm are derived using the received positional signal. The position values at time intervals T1 through Tmxe2x88x921 are filtered with a predictive filter to derive predicted position values of the mobile receiver at time intervals T1 through Tmxe2x88x921. A first positional error indicative of a low frequency noise component reducing the accuracy of the position values and predicted position values at time intervals T1 through Tm is derived using predicted position values T1 through Tmxe2x88x921. The position value at time interval Tm is corrected with the first positional error to derive a corrected position value at time interval Tm. The corrected position value at time interval Tm is predictively filtered to derive a predicted position of the mobile receiver at time interval Tm, the predicted position at time interval Tm being substantially free of the low frequency noise component.
In accordance with another aspect of the present invention, a method of accurately determining the position of a mobile receiver includes receiving a positional signal and deriving position values of the mobile receiver using the positional signal. The position values are applied to a predictive filter to derive predicted position values of the mobile receiver. A turn of the mobile receiver is detected using the predicted position values and a first positional offset associated with the turn is derived. The first positional offset represents a low frequency noise component corrupting the positional accuracy of the received signal. Position values derived after the turn is detected are corrected using the first positional offset to derive corrected position values. A second positional offset is derived between each of the corrected position values and a navigable route coinciding with where the mobile receiver is probably located for each of the corrected position values. The second positional offset represents a high frequency noise corrupting the positional accuracy of the received signal. Each of the corrected position values is applied along with the second positional offset associated with each of the corrected position values to the predictive filter to derive predicted position values substantially free of the low frequency and high frequency noise.
In yet another aspect of the present invention, an article is disclosed including at least one sequence of machine executable instructions. A medium bears the executable instructions in machine readable form, wherein execution of the instructions by one or more processors causes the one or more processors to seed a predictive filter with an initial value indicative of an erroneous current position value of the MR displaced a predetermined minimum distance from a known approximate position of the MR to establish an initial gain of the predictive filter. The one or more processors receives a positional signal over m time periods and derives position values of the MR over the m time periods using the received signal. The one or more processors derives predicted position values of the MR over the m time periods by predictively filtering the position values with the predictive filter, and determines a probable position of the MR at an end of the m time periods using a current predicted position value, the probable position coinciding with a navigable route of where the MR is probably positioned at the end of the m time periods.
In a further aspect of the present invention, an article is disclosed including at least one sequence of machine executable instructions and a medium bearing the executable instructions in machine readable form, wherein execution of the instructions by one or more processors causes the one or more processors to detect a turn of the MR using a received positional signal having a positional accuracy corrupted by relatively low and high frequency noise components, and derive a first positional offset associated with the turn and representative of the low frequency noise component. The one or more processors derive a position value of the MR using the received positional signal after detecting the turn, and correct the position value with the first positional offset associated with the turn to derive a corrected position value. The one or more processors apply the corrected position value to a filter along with a second positional offset associated with the corrected position value and representative of the high frequency noise component to derive a filtered position value substantially free of the low and high frequency noise components.
In an even further aspect of the present invention, a computer architecture is disclosed including seeding means for seeding a predictive filter with an initial value indicative of an erroneous current position value of the MR displaced a predetermined minimum distance from a known approximate position of the MR to establish an initial gain of the predictive filter. Receiving means are provided for receiving a positional signal over m time periods and for deriving position values of the MR over the m time periods using the received signal. Deriving means are provided for deriving predicted position values of the MR over the m time periods by predictively filtering the position values with the predictive filter. Determining means are provided for determining a probable position of the MR at an end of the m time periods using a current predicted position value, the probable position coinciding with a navigable route of where the MR is probably positioned at the end of the m time periods.
In another aspect of the present invention, a computer architecture is disclosed including detecting means for detecting a turn of the MR using a received positional signal having a positional accuracy corrupted by relatively low and high frequency noise components, and for deriving a first positional offset associated with the turn and representative of the low frequency noise component. Deriving means are provided for deriving a position value of the MR using the received positional signal after detecting the turn, and correcting means are provided for correcting the position value with the first positional offset associated with the turn to derive a corrected position value. Applying means are provided for applying the corrected position value to a filter along with a second positional offset associated with the corrected position value and representative of the high frequency noise component to derive a filtered position value substantially free of the low and high frequency noise components.
In yet another aspect of the present invention, a computer system is disclosed including a processor and a memory coupled to the processor, the memory having stored therein sequences of instructions, which, when executed by the processor, cause the processor to perform the step of seeding a predictive filter with an initial value indicative of an erroneous current position value of the MR displaced a predetermined minimum distance from a known approximate position of the MR to establish an initial gain of the predictive filter. The processor receives a positional signal over m time periods and derives position values of the MR over the m time periods using the received signal. The processor derives predicted position values of the MR over the m time periods by predictively filtering the position values with the predictive filter, and determines a probable position of the MR at an end of the m time periods using a current predicted position value, the probable position coinciding with a navigable route of where the MR is probably positioned at the end of the m time periods.
In another aspect of the present invention, a computer system is disclosed including a processor and a memory coupled to the processor, the memory having stored therein sequences of instructions, which, when executed by the processor, cause the processor to perform the steps of detecting a turn of the MR using a received positional signal having a positional accuracy corrupted by relatively low and high frequency noise components, and deriving a first positional offset associated with the turn and representative of the low frequency noise component. The processor derives a position value of the MR using the received positional signal after the turn is detected, and corrects the position value with the first positional offset associated with the turn to derive a corrected position value. The processor applies the corrected position value to a filter along with a second positional offset associated with the corrected position value and representative of the high frequency noise component to derive a filtered position value substantially free of the low and high frequency noise components.
Still other objects and advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description, wherein only the preferred embodiments of the invention are shown and described, simply by way of illustration of the best mode contemplated of carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive.